package com.zang.greedy;

/**
 * @author Cizai
 * @since 2022/11/25 22:04
 * @see <a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/">...</a>
 **/
public class 买卖股票的最佳时机 {

    // 贪心
    public int maxProfit(int[] prices) {
        if(prices.length <= 1) return 0;
        // 记录最小值
        int min = prices[0];
        // 记录最大利润
        int maxMoney = Integer.MIN_VALUE;

        for (int i = 1; i < prices.length; i++) {
            if (i==1){
                maxMoney = Math.max(maxMoney,prices[i]-prices[i-1]);
            }else {
                maxMoney = Math.max(maxMoney,prices[i]-min);
            }

            min = Math.min(min,prices[i]);
        }
        return Math.max(maxMoney, 0);
    }
    public int maxProfitDP(int[] prices) {
        if(prices.length <= 1) return 0;
        // 记录最小值
        int min = prices[0];
        // 记录最大利润
        int[] dp = new int[prices.length];

        for (int i = 1; i < prices.length; i++){
            // 拿到最小值
            min = Math.min(min, prices[i]);
            // 上一个点的最大利润和当前的利润哪个大取大的
            dp[i] = Math.max(dp[i - 1], prices[i] - min);
        }
        return dp[prices.length - 1];
    }
}
